package main.old.new_2023.last.month_6;

import main.dataStruct.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Description:
 * todo 1262. 可被三整除的最大和
 * 给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
 *
 * todo 剑指 Offer 32 - III. 从上到下打印二叉树 III
 * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 *
 * todo 剑指 Offer 26. 树的子结构
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0619 {

    //树的子结构
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

    //从上到下打印二叉树
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        //使用双端队列
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null){
            return lists;
        }
        queue.offer(root);
        int temp =0;
        while (queue.size() != 0){
            LinkedList<Integer> tmp = new LinkedList<>();
            for (int i = queue.size();i>0;i--){
                TreeNode poll = queue.poll();
                if (temp %2 == 0){
                    tmp.add(poll.val);
                }else {
                    tmp.addFirst(poll.val);
                }
                if (poll.left != null){
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    queue.offer(poll.right);
                }
            }
            temp++;
            lists.add(tmp);
        }
        return lists;
    }

    //可被三整除的最大和
    public int maxSumDivThree(int[] nums) {
        //贪心算法,首先nums分为3个数组，除3取模，a =0，全部拿下，b = 1,c=2。最后判断所有数组加起来取模剩多少，以此判断最大和
        if (nums.length  == 0){
            return 0;
        }
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        List<Integer> c = new ArrayList<>();
        int sum = 0;
        for (int num:nums){
            sum +=num;
            int mole = num % 3 ;
            if (mole ==0){
                a.add(num);
            }else if (mole == 1){
                b.add(num);
            }else {
                c.add(num);
            }
        }
        int value = sum % 3;
        int shenyu = sum;
        if (value ==2){
            //取b的 前两个 或者 c 的一个
            if (b.size() >1){
                b = b.stream().sorted().collect(Collectors.toList());
                shenyu = b.get(0) + b.get(1);
            }
            if (c.size() >0){
                c = c.stream().sorted().collect(Collectors.toList());
                if (c.get(0) < shenyu){
                    shenyu = c.get(0);
                }
            }
        }else if (value == 1){
            //取b的一个 或者 c的两个
            if (b.size() >0){
                b = b.stream().sorted().collect(Collectors.toList());
                shenyu = b.get(0);
            }
            if (c.size() >1){
                c = c.stream().sorted().collect(Collectors.toList());
                if (c.get(0) + c.get(1) < shenyu){
                    shenyu = c.get(0) + c.get(1);
                }
            }
        }else {
            shenyu = 0;
        }
        return sum - shenyu;
    }

}
